/*
 * @lc app=leetcode.cn id=74 lang=golang
 *
 * [74] 搜索二维矩阵
 */

// 2. 转成一维数组再使用二分
// @lc code=start
func searchMatrix(matrix [][]int, target int) bool {
	array := []int{}
	for i := 0; i < len(matrix); i++ {
		array = append(array, matrix[i]...)
	}

	l, r := 0, len(array)-1
	for l <= r {
		mid := (l + r) / 2
		if array[mid] == target {
			return true
		}

		if array[mid] > target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return false
}

// @lc code=end

// 1. 二分，在二维矩阵搜索
// @lc code=start
func searchMatrix(matrix [][]int, target int) bool {
	row := len(matrix)       // 行数
	column := len(matrix[0]) // 列数
	l, r := 0, row*column

	for l <= r {
		mid := (l + r) / 2

		if mid == 0 && matrix[0][0] == target {
			return true
		}

		if mid == 0 && matrix[0][0] != target {
			return false
		}

		var x int
		var y int
		if mid%column != 0 {
			x = mid / column
			y = mid%column - 1
		} else {
			x = mid/column - 1
			y = column - 1
		}
		if matrix[x][y] == target {
			return true
		}
		if matrix[x][y] > target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}

	return false
}

// @lc code=end

